package com.test.leetcode;

/**
 * https://leetcode.cn/problems/maximal-square/description/
 * @author sujiafa
 * @date 2025/4/10
 */
public class n221_最大正方形 {

    public int maximalSquare(char[][] matrix) {
        // 线性DP知识二例题
        // 1. 定义状态
        // 设dp[i][j]表示以(i, j)为右下角的最大正方形的边长
        // 2. 状态转移方程
        // 2.1 对于矩阵中的每个位置(i, j)，如果matrix[i][j] == '1'，那么dp[i][j]的值取决于其左上方dp[i - 1][j - 1]、上方dp[i - 1][j]
        // 和左方dp[i][j - 1]这三个位置的dp值。具体来说，dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1。
        // 这是因为以(i, j)为右下角的最大正方形的边长，受到其左上方、上方和左方三个方向上的最大正方形边长的限制，取这三个方向边长的最小值再加 1，
        // 就是当前位置能构成的最大正方形边长。
        // 2.2 如果matrix[i][j] == '0'，那么dp[i][j] = 0，因为当前位置为0无法构成包含'1'的正方形。
        // 3. 初始化状态
        // 对于矩阵的第一行和第一列，如果matrix[i][0] == '1'，则dp[i][0] = 1；否则dp[i][0] = 0。同理，对于矩阵的第一列，
        // 如果matrix[0][j] == '1'，则dp[0][j] = 1；否则dp[0][j] = 0 。
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];

        int maxSize = 0;
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxSize = 1;
            }
        }
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                maxSize = 1;
            }
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                    maxSize = Math.max(maxSize, dp[i][j]);
                }
            }
        }

        return maxSize * maxSize;
    }
}
